package similarity.simiMatrix;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.StringTokenizer;

import org.dom4j.Document;
import org.dom4j.DocumentException;
import org.dom4j.Element;
import org.dom4j.io.SAXReader;

import preprocess.Arith;

/**
 * Calculate similarity matrix through evaluate the distance between each pair
 * of elements and the elements' depth in DTD DOM tree
 * 
 * @author eDisOn
 * @version 0.1
 */

@SuppressWarnings("unused")
public class CalcSimMatrixByPathDist implements SimilarityMatrix
{
    /* Project root path */
    private final static String ROOT                  = utils.Configuration.RootPath;

    /* Similarity matrix file path */
    private final static String SIMI_MATRIX_FILE_PATH = ROOT;

    /* DTD file */
    private Document            DTD                   = null;

    /* The total number of elements in this DTD file */
    private int                 totalElemNum          = 0;

    /*
     * DFSLableIndex is used to assist DFS process to set label to each element
     * in DFS traversal
     */
    private int                 DFSLableIndex         = 0;

    /*
     * matrixLabel record the elements name in it according to element's DFS
     * order
     */
    private String[]            matrixLabel           = null;

    /* depthLabel is used to record the depth information for all elements */
    private int[]               depthLabel            = null;

    /* simiMatrix record the similarity between each pair of elements */
    double[][]                  simiMatrix            = null;

    /**
     * Default construction used when similarity matrix has been calculated and
     * saved into local disk, and user just want to load it into memory.
     */
    public CalcSimMatrixByPathDist()
    {

    }

    /**
     * Construction with DTD parameter
     */
    public CalcSimMatrixByPathDist(Document DTD)
    {
        /* get the total element number info */
        this.DTD = DTD;
        this.totalElemNum = 1 + this.calcElemNum(this.DTD.getRootElement());

        /* first create a matrix table */
        this.simiMatrix = new double[this.totalElemNum][this.totalElemNum + 1];

        /*
         * matrixLabel is used to record the labels name which consisted with
         * the elements' name and depth information(For example: if element A is
         * in the root element, then its name in matrixLabel is A_1). It's index
         * is its appearance order in DFS traversal order
         */
        this.matrixLabel = new String[this.totalElemNum];

        /* depthLabel is used to record depth information for each element */
        this.depthLabel = new int[this.totalElemNum];
    }

    /**
     * Calculate similarity matrix through two times DFS(NLR preorder traversal)
     * and one time postorder traversal
     * 
     * @param trainDocList
     *            training xml document set
     * @param DTD
     *            DTD file
     * 
     * @return true if calculate succeed, false otherwise
     */
    public boolean calcSimMatrix(ArrayList<Document> trainDocList, Document DTD)
    {
        try
        {
            /* DFS(1) - find distance to parent */
            Element root = DTD.getRootElement();
            this.matrixLabel[0] = root.getName();
            this.depthLabel[0] = 1;
            this.DFSExplore(root, simiMatrix, matrixLabel, 1);

            /*
             * LRN - explore all descendant of each element by postorder
             * traversal
             */
            Node rootNode = new Node(root.getName());
            this.exploreDescendant(root, rootNode);

            /* DFS(2) - find distance between each pair of elements */
            this.exploreDistance(rootNode);

            /*
             * Calculate similarity between each pair of elements according the
             * formula Sij = 2exp(-distance(ei,ej)) 10exp(-(depth(ei) +
             * depth(ej)))
             */
            this.calcSimilarity();

            return true;
        }
        catch (Exception ex)
        {
            ex.printStackTrace();
            return false;
        }
    }

    /**
     * Explore the distance from each ascendant to their descendant, and explore
     * all elements' level in DTD DOM tree
     * 
     * @param elem
     *            ascendant element
     * @param simiMatrix
     *            similarity matrix
     * @param matrixLabel
     *            current matrix label index
     * @param depth
     *            depth information
     */
    private void DFSExplore(Element elem, double[][] simiMatrix,
            String[] matrixLabel, int depth)
    {
        int currIndex = this.DFSLableIndex;

        for (Iterator it = elem.elementIterator(); it.hasNext();)
        {
            this.DFSLableIndex++;
            int currentChildIndex = this.DFSLableIndex;
            Element child = (Element) it.next();
            matrixLabel[currentChildIndex] = child.getName();
            this.depthLabel[currentChildIndex] = depth + 1;

            simiMatrix[currIndex][currentChildIndex] = 1;
            this.DFSExplore(child, simiMatrix, matrixLabel, depth + 1);

            int pos = currentChildIndex + 1;
            while (simiMatrix[currentChildIndex][pos] != 0)
            {
                simiMatrix[currIndex][pos] = 1 + simiMatrix[currentChildIndex][pos];
                pos++;
            }
        }
    }

    /**
     * Find all descendant name of parent element through postorder traversal
     * 
     * @param parent
     *            the parent element
     * @param parentNode
     *            the parent node
     */
    private void exploreDescendant(Element parent, Node parentNode)
    {
        /* postorder traversal */
        ArrayList<Node> children = new ArrayList<Node>();
        for (Iterator it = parent.elementIterator(); it.hasNext();)
        {
            Element child = (Element) it.next();
            Node childNode = new Node(child.getName());
            exploreDescendant(child, childNode);
            children.add(childNode);
        }

        /* get descendant name including children and their descendant */
        for (Node child : children)
        {
            parentNode.addDescNameList(child.getChildrenNameList());
            parentNode.addDescName(child.getName());
        }

        parentNode.setChildrenNode(children);
    }

    /**
     * Calculate distance between each pair of elements
     * 
     * @param elemNode
     *            root node in DFS traversal
     */
    private void exploreDistance(Node elemNode)
    {
        /* explore all children's descendant name list */
        ArrayList<ArrayList<String>> nameSet = new ArrayList<ArrayList<String>>();
        ArrayList<Node> childrenNode = elemNode.getChildrenNode();
        for (Iterator nodeIt = childrenNode.iterator(); nodeIt.hasNext();)
        {
            Node childNode = (Node) nodeIt.next();
            ArrayList<String> nameList = childNode.getChildrenNameList();
            nameList.add(childNode.getName());
            nameSet.add(nameList);
        }

        /*
         * calculate distance between each pair of descendant which in different
         * branches
         */
        int currElemMatrixLabelIndex = this.findElemMatrixLabelIndex(elemNode
                .getName());
        for (int a = 0; a < nameSet.size(); a++)
        {
            ArrayList<String> leftBranch = nameSet.get(a);
            for (int b = a + 1; b < nameSet.size(); b++)
            {
                ArrayList<String> rightBranch = nameSet.get(b);

                for (String leftElem : leftBranch)
                {
                    int left = this.findElemMatrixLabelIndex(leftElem);
                    for (String rightElem : rightBranch)
                    {
                        int right = this.findElemMatrixLabelIndex(rightElem);

                        int dist = this.calcDistance(left, right,
                                currElemMatrixLabelIndex);

                        if (left < right)
                        {
                            this.simiMatrix[left][right] = dist;
                        }
                        else
                        {
                            this.simiMatrix[right][left] = dist;
                        }
                    }
                }
            }
        }

        /* invoke each children node DFS traversal process */
        for (Iterator nodeIt = childrenNode.iterator(); nodeIt.hasNext();)
        {
            Node child = (Node) nodeIt.next();
            this.exploreDistance(child);
        }
    }

    /**
     * Calculate similarity between each pair of elements according the formula
     * Sij = 2exp(-distance(ei,ej)) * 10*exp(-(depth(ei) + depth(ej)))
     * 
     * @return true if calculate succeed, false otherwise
     */
    private boolean calcSimilarity()
    {
        try
        {
            for (int index = 0; index < this.totalElemNum; index++)
            {
                for (int pos = index; pos < this.totalElemNum; pos++)
                {
                    double distance = this.simiMatrix[index][pos];
                    int depthE1 = this.depthLabel[index];
                    int depthE2 = this.depthLabel[pos];

                    double similarity = Math.pow(2, 0 - distance)
                            * Math.pow(10, 0 - (depthE1 + depthE2));
                    this.simiMatrix[index][pos] = Arith.round(similarity, 10);
                }
            }
            return true;
        }
        catch (Exception ex)
        {
            return false;
        }
    }

    /**
     * Find matrix label of this element
     * 
     * @param elemName
     *            element name
     * @return matrix label according to this element name
     */
    private int findElemMatrixLabelIndex(String elemName)
    {
        for (int index = 0; index < this.matrixLabel.length; index++)
        {
            if (elemName.equals(this.matrixLabel[index])) { return index; }
        }
        return -1;
    }

    /**
     * Calculate distance between each pair of matrix labels
     * 
     * @param left
     *            left label
     * @param right
     *            right label
     * @param root
     *            common ascendant root of left and right
     * @return the distance between left label and right label
     */
    private int calcDistance(int left, int right, int root)
    {
        int distance = -1;

        int leftDist = (int) this.simiMatrix[root][left];
        int rightDist = (int) this.simiMatrix[root][right];

        distance = leftDist + rightDist;

        return distance;
    }

    /**
     * Calculate all descendant element number in this element object
     * 
     * @param elem
     *            Element object
     * @return the all descendant element number in this element object
     */
    private int calcElemNum(Element elem)
    {
        int childrenNum = 0;
        for (Iterator it = elem.elementIterator(); it.hasNext();)
        {
            this.calcElemNum((Element) it.next());
            childrenNum++;
        }

        this.totalElemNum += childrenNum;
        return this.totalElemNum;
    }

    /**
     * Get similarity matrix
     * 
     * @return similarity matrix
     */
    public double[][] getSimilarityMatrix()
    {
        return this.simiMatrix;
    }

    /**
     * Display the similarity matrix
     */
    public void displaySimiMatrix()
    {
        for (int i = 0; i < this.totalElemNum; i++)
        {
            for (int j = 0; j < this.totalElemNum; j++)
            {
                System.out.print(this.simiMatrix[i][j] + "\t");
            }
            System.out.println();
        }
    }

    /**
     * Save the similarity matrix content to local disk
     * 
     * @param simiMatrixPath
     *            the similarity matrix file path in local disk
     * @return true if save succeed, false otherwise
     */
    public boolean saveSimilarityMatrix()
    {
        try
        {
            FileWriter fw = new FileWriter(this.SIMI_MATRIX_FILE_PATH);
            PrintWriter fpw = new PrintWriter(fw);

            /* Write the matrix label info into first line */
            for (int i = 0; i < this.totalElemNum; i++)
            {
                fpw.print(this.matrixLabel[i] + "\t");
            }
            fpw.println();

            /* Write the depth info into second line */
            for (int i = 0; i < this.totalElemNum; i++)
            {
                fpw.print(this.depthLabel[i] + "\t");
            }
            fpw.println();

            /* Write the similarity value into file */
            for (int i = 0; i < this.totalElemNum; i++)
            {
                for (int j = 0; j < this.totalElemNum; j++)
                {
                    fpw.print(this.simiMatrix[i][j] + "\t");
                }
                fpw.println();
            }
            fpw.close();
            fw.close();
            return true;
        }
        catch (IOException ioe)
        {
            ioe.printStackTrace();
            return false;
        }
    }

    /**
     * Load the similarity matrix content from local disk
     * 
     * @param simiMatrixPath
     *            the similarity matrix file path in local disk
     * @return true if load succeed, false otherwise
     */
    public boolean loadSimilarityMatrix()
    {
        try
        {
            BufferedReader fr = new BufferedReader(new FileReader(
                    this.SIMI_MATRIX_FILE_PATH));

            /* get total element number */
            String line = fr.readLine();
            StringTokenizer stk = new StringTokenizer(line, "\t");
            this.totalElemNum = stk.countTokens();

            /* load matrix label info */
            this.matrixLabel = new String[this.totalElemNum];
            int index = 0;
            while (stk.hasMoreTokens())
            {
                this.matrixLabel[index] = stk.nextToken();
                index++;
            }

            /* load depth info */
            this.depthLabel = new int[this.totalElemNum];
            line = fr.readLine();
            stk = new StringTokenizer(line, "\t");
            index = 0;
            while (stk.hasMoreTokens())
            {
                this.depthLabel[index] = Integer.parseInt(stk.nextToken());
                index++;
            }

            /* load similarity value */
            this.simiMatrix = new double[this.totalElemNum][this.totalElemNum];
            index = 0;
            while ((line = fr.readLine()) != null)
            {
                stk = new StringTokenizer(line, "\t");

                int pos = 0;
                while (stk.hasMoreTokens())
                {
                    this.simiMatrix[index][pos] = Double.parseDouble(stk
                            .nextToken());
                    pos++;
                }
                index++;
            }

            fr.close();
            return true;
        }
        catch (IOException ioe)
        {
            ioe.printStackTrace();
            return false;
        }
    }

//    // TODO: Test function
//    public static void main(String[] args) throws DocumentException
//    {
//        SAXReader saxReader = new SAXReader();
//        Document document = saxReader.read(ROOT + "data/dtd/DTD.xml");
//
//        CalcSimMatrixByPathDist calcByDist = new CalcSimMatrixByPathDist(
//                document);
//        calcByDist.calcSimMatrix(null, document);
//        calcByDist.displaySimiMatrix();
//        calcByDist.saveSimilarityMatrix();
//        // CalcSimMatrixByPathDist calcByDist = new CalcSimMatrixByPathDist();
//        // calcByDist.loadSimilarityMatrix();
//    }
}

/**
 * JAVA bean
 * 
 * @author eDisOn
 * 
 */
class Node
{
    String            nodeName     = "";
    ArrayList<String> descendant   = null;
    ArrayList<Node>   childrenNode = null;

    public Node(String name)
    {
        this.nodeName = name;
        this.descendant = new ArrayList<String>();
    }

    public String getName()
    {
        return this.nodeName;
    }

    public void addDescName(String desc)
    {
        this.descendant.add(desc);
    }

    public void addDescNameList(ArrayList<String> descList)
    {
        for (String desc : descList)
        {
            this.descendant.add(desc);
        }
    }

    public ArrayList<String> getChildrenNameList()
    {
        return this.descendant;
    }

    public void setChildrenNode(ArrayList<Node> children)
    {
        this.childrenNode = children;
    }

    public ArrayList<Node> getChildrenNode()
    {
        return this.childrenNode;
    }
}
